package org.company.earth.arithmetic;

import java.util.List;

public class BubbleSort<T> extends BaseSort<T> {
    
    /**
     * 双向循环排序列表
     * @description 冒泡排序
     */
    @Override
    public void sort(List<T> list) {
        this.bubbleSort1(list);
    }
    
    /**
     * 简单冒泡排序,O(N^2)
     * @param list
     */
    public void bubbleSort(List<T> list) {
        for(int i = 0 ; i < list.size()-1;i++) {
            for(int j=0 ; j < list.size() - i - 1 ; j++) {
                if(this.gt(list.get(j), list.get(j+1))) {
                    this.swap(list, j, j+1);
                }
            }
            this.print(list);
        }
    }
    
    /**
     * 标记冒泡排序,时间复杂度 O(n(n+1)/2)
     * @param list
     */
    public void bubbleSort1(List<T> list) {
        int length = list.size();
        int i = length - 1;
        while(i > 0) {
            int pos = 0;
            for(int j = 0 ; j < i ; j++) {
                if(this.gt(list.get(j), list.get(j+1))) {
                    pos = j;
                    this.swap(list, j, j+1);
                }
            }
            i = pos;
            this.print(list);
        }
    }
    
    public void bubbleSort2(List<T> list) {
        int length = list.size();
        while(length > 1) {
            for(int i = 0 ; i < length - 2 ; i++) {
                if(this.gt(list.get(i), list.get(i+1))) {
                    this.swap(list, i, i+1);
                }
            }
        }
    }
    
}
